package org.example.myleet.p781;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Solution {
    /**
     * 3 ms
     * 贪心算法，将所有回答数目相同的兔子先聚在一起，再统计出有多少种颜色的兔子
     */
    public int numRabbits(int[] answers) {
        if (answers.length == 0) {
            return 0;
        }
        Arrays.sort(answers);
        int sum = 0;
        List<RabbitColor> colors = new ArrayList<>();
        RabbitColor color = new RabbitColor(answers[0] + 1);
        colors.add(color);
        for (int i = 1; i < answers.length; ++i) {
            RabbitColor c = colors.get(colors.size() - 1);
            if (c.total != answers[i] + 1) {
                //报的数目不同，是另一种颜色的兔子
                colors.add(new RabbitColor(answers[i] + 1));
                continue;
            }
            if (c.isAllFound()) {
                //已经找到所有相同颜色的兔子，新建一种颜色
                colors.add(new RabbitColor(answers[i] + 1));
                continue;
            }
            //相同颜色的兔子出现并且此种颜色的兔子未完全找到
            ++c.occur;
        }
        for (int i = 0; i < colors.size(); ++i) {
            //统计所有颜色的兔子
            sum += colors.get(i).total;
        }
        return sum;
    }

    static class RabbitColor {
        int total;
        int occur;

        public RabbitColor(int total) {
            this.total = total;
            this.occur = 1;
        }

        public boolean isAllFound() {
            return occur >= total;
        }
    }
}
